<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<html><head>
<!--Converted with LaTeX2HTML 98.1 release (February 19th, 1998)
originally by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds
* revised and updated by:  Marcus Hennecke, Ross Moore, Herb Swan
* with significant contributions from:
  Jens Lippmann, Marek Rouchal, Martin Wilck and others -->


<title>Parentheses Balance</title>
<meta name="description" content="Parentheses Balance">
<meta name="keywords" content="htmlatex">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<link rel="STYLESHEET" href="acm-00673_files/htmlatex.css">
</head><body bgcolor="#ffffff" lang="EN">

<h1><br clear="all"><center><table bgcolor="#0060f0"><tbody><tr><td><b><font color="#c0ffff" size="5">&nbsp;<a name="SECTION0001000000000000000000">
Parentheses Balance</a>&nbsp;</font></b></td></tr></tbody></table></center>
</h1>

<p>
You are given a string consisting of parentheses <tt>()</tt> and <tt>[]</tt>.    A
string of this type is said to be <em>correct</em>:
</p><dl compact="compact">
<dt>(a)
</dt><dd>if it is the empty string
</dd><dt>(b)
</dt><dd>if A and B are correct, AB is correct,
</dd><dt>(c)
</dt><dd>if A is correct, <tt>(</tt>A<tt>)</tt> and <tt>[</tt>A<tt>]</tt> is correct.
</dd></dl>

<p>
Write a program that takes a sequence of strings of this type and check
their correctness. Your program can assume that the maximum string
length is 128.

</p><p>

</p><h2><font color="#0070e8"><a name="SECTION0001001000000000000000">
Input</a>&nbsp;</font>
</h2>
The file contains a positive integer <i>n</i> and a sequence of <i>n</i> strings of
parentheses <tt>()</tt> and <tt>[]</tt>, one string a line.

<p>

</p><h2><font color="#0070e8"><a name="SECTION0001002000000000000000">
Output</a>&nbsp;</font>
</h2>
A sequence of <tt>Yes</tt> or <tt>No</tt> on the output file.

<p>

</p><h2><font color="#0070e8"><a name="SECTION0001003000000000000000">
Sample Input</a>&nbsp;</font>
</h2>

<p>
</p><pre>3
([])
(([()])))
([()[]()])()
</pre>

<p>

</p><h2><font color="#0070e8"><a name="SECTION0001004000000000000000">
Sample Output</a>&nbsp;</font>
</h2>
				
<pre>Yes
No
Yes
</pre>

<p>

</p><p>
<br></p><hr>
<address>
<i>Miguel Revilla</i>
<br><i>2000-08-14</i>
</address>
</body></html>